public class Solution {
    public static int findLCS(String A,int n, String B, int m){
        int max=0;
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        int[][] dp = new int[n+1][m+1];
        for(int i=0;i<=n;i++)
            dp[i][0]=0;
        for(int j=0;j<=m;j++)
            dp[0][j]=0;
        for(int i=0;i<n;i++){
            for(int j=0; j<m; j++){
                if(a[i]==b[j])
                    dp[i+1][j+1] = dp[i][j]+1;
                else{
                    dp[i+1][j+1] = dp[i][j+1]>dp[i+1][j]?dp[i][j+1]:dp[i+1][j];
                }
                if(dp[i+1][j+1]>max)
                    max = dp[i+1][j+1];
            }
        }
        return max;
    }
    public static int findLCSR(String A, int n, String B, int m) {
        int c1, c2;
        if(n==0 ||m==0)return 0;
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        if(a[n-1]==b[m-1])
            return findLCSR(A,n-1,B,m-1)+1;
        else{
            c1 = findLCSR(A,n,B,m-1);
            c2 = findLCSR(A,n-1,B,m);
            return c1>c2?c1:c2;
        }
    }
    public static void main(String args[]){
        String a = "1A2C3D4B56";
        String b = "B1D23CA45B6A";
        int c = findLCS(a,a.length(),b,b.length());
        System.out.println(c);
    }

}

